#include "train.h"

class Solution {
public:
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        typedef pair<int, int> PII;
        int n = lists.size();
        set<PII> s;
        for (int i = 0; i < n; i++)
        {
            if (lists[i] == nullptr) continue; //防止为空
            s.insert(PII(lists[i]->val, i));
        }
        ListNode new_head, * p = &new_head,*q; // p指向结果链表的最后一位
        new_head.next = nullptr;

        while (s.size())
        {
            PII a = *s.begin(); // 取出第一个链表的第一个结点
            s.erase(s.begin());
            q = lists[a.second]; // 表示它在第几个链表中的第一个结点
            lists[a.second] = lists[a.second]->next; //删除该链表
            p->next = q;
            q->next = nullptr;
            p = q;
            if (lists[a.second])
            {
                s.insert(PII(lists[a.second]->val, a.second)); //该节点的值 以及所在链表编号
            }

        }
        return new_head.next;
    }   
};